import java.util.HashMap;
import java.util.Map;

/**
 * 1218.最长定差子序列
 */
public class Exerciser5 {
    public int longestSubsequence(int[] arr, int difference) {
        // dp[i]: 以i位置为结尾的所有子序列中，最长定差子序列的长度
        // 因为arr[i] - difference 是一个定值是知道多少的值，可以在i之前直接找到，所以不需要进行遍历，直接进行寻找就可以了利用哈希表
        // 这里保存的是: arr[i],dp[i]
        Map<Integer,Integer> hash = new HashMap<>();
        int ret = 1;
        for(int x : arr) {
            hash.put(x,hash.getOrDefault(x - difference,0) + 1);
            ret = Math.max(ret,hash.get(x));
        }
        return ret;
    }
}
